import re
import lcs

pinyin_dict = {
    'a': ['a'],
    'an': ['ang', 'an'],
    'ai': ['ai'],
    'ao': ['ao'],

    'ba': ['bang', 'bai', 'ban', 'bao', 'ba'],
    'be': ['beng', 'bei', 'ben'],
    'bi': ['bing', 'bian', 'biao', 'bie', 'bin', 'bi'],
    'bo': ['bo'],
    'bu': ['bu'],

    'ca': ['cang', 'cai', 'can', 'cao', 'ca'],
    'ce': ['ceng', 'cen', 'ce'],
    'ch': ['chuang', 'cheng', 'chang', 'chong', 'chuai', 'chuan', 'chai', 'chua', 'chui', 'chun', 'chuo', 'chan',
           'chao', 'chen', 'chou', 'cha', 'che', 'chi', 'chu'],
    'ci': ['ci'],
    'co': ['cong', 'cou'],
    'cu': ['cuan', 'cui', 'cun', 'cuo', 'cu'],

    'da': ['dang', 'dai', 'dan', 'dao', 'da'],
    'de': ['deng', 'dei', 'den', 'de'],
    'di': ['ding', 'dian', 'diao', 'dia', 'die', 'diu', 'di'],
    'do': ['dong', 'dou'],
    'du': ['duan', 'dui', 'dun', 'duo', 'du'],

    'e': ['e'],
    'ei': ['ei'],
    'en': ['eng', 'en'],
    'er': ['er'],

    'fa': ['fang', 'fan', 'fa'],
    'fe': ['feng', 'fei', 'fen'],
    'fo': ['fou', 'fo'],
    'fu': ['fu'],

    'ga': ['gang', 'gai', 'gan', 'gao', 'ga'],
    'ge': ['geng', 'gei', 'gen', 'ge'],
    'go': ['gong', 'gou'],
    'gu': ['guang', 'guai', 'guan', 'gua', 'gui', 'gun', 'guo', 'gu'],

    'ha': ['hang', 'hai', 'han', 'hao', 'ha'],
    'he': ['heng', 'hei', 'hen', 'he'],
    'ho': ['hong', 'hou'],
    'hu': ['huang', 'huai', 'huan', 'hua', 'hui', 'hun', 'huo', 'hu'],

    'ji': ['jiang', 'jiong', 'jing', 'jian', 'jiao', 'jia', 'jie', 'jin', 'jiu', 'ji'],
    'ju': ['juan', 'jue', 'jun', 'ju'],

    'ka': ['kang', 'kai', 'kan', 'kao', 'ka'],
    'ke': ['keng', 'ken', 'ke'],
    'ko': ['kong', 'kou'],
    'ku': ['kuang', 'kuai', 'kuan', 'kua', 'kui', 'kun', 'kuo', 'ku'],

    'la': ['lang', 'lai', 'lan', 'lao', 'la'],
    'le': ['leng', 'lei', 'le'],
    'li': ['liang', 'ling', 'lian', 'liao', 'lia', 'lie', 'lin', 'liu', 'li'],
    'lo': ['long', 'lou'],
    'lu': ['luan', 'lue', 'lun', 'luo', 'lu'],
    'lv': ['lve', 'lv'],

    'm': ['m'],
    'ma': ['mang', 'mao', 'mai', 'man', 'ma'],
    'me': ['meng', 'mei', 'men', 'me'],
    'mi': ['ming', 'mian', 'miao', 'mie', 'min', 'miu', 'mi'],
    'mo': ['mo', 'mou'],
    'mu': ['mu'],

    'na': ['nang', 'nai', 'nan', 'nao', 'na'],
    'ne': ['neng', 'nei', 'nen', 'ne'],
    'ni': ['niang', 'ning', 'nian', 'niao', 'nie', 'nin', 'niu', 'ni'],
    'no': ['nong', 'nou'],
    'nu': ['nuan', 'nuo', 'nun', 'nu'],
    'nv': ['nve', 'nv'],

    'o': ['o'],
    'ou': ['ou'],

    'pa': ['pang', 'pao', 'pai', 'pan', 'pa'],
    'pe': ['peng', 'pei', 'pen'],
    'pi': ['ping', 'pian', 'piao', 'pie', 'pin', 'pi'],
    'pu': ['po', 'pou'],
    'po': ['pu'],

    'qi': ['qiong', 'qiang', 'qing', 'qiao', 'qian', 'qie', 'qin', 'qia', 'qiu', 'qi'],
    'qu': ['quan', 'que', 'qun', 'qu'],

    'ra': ['rang', 'ran', 'rao'],
    're': ['reng', 'ren', 're'],
    'ri': ['ri'],
    'ro': ['rong', 'rou'],
    'ru': ['ruan', 'rui', 'run', 'ruo', 'ru'],

    'sa': ['sang', 'sai', 'san', 'sao', 'sa'],
    'se': ['seng', 'sen', 'se'],
    'sh': ['shuang', 'sheng', 'shang', 'shuai', 'shuan', 'shai', 'shan', 'shao', 'shei', 'shen', 'shua', 'shui', 'shun',
           'shuo', 'shou', 'sha', 'she', 'shi', 'shu'],
    'si': ['si'],
    'so': ['song', 'sou'],
    'su': ['suan', 'sui', 'sun', 'suo', 'su'],

    'ta': ['tang', 'tai', 'tan', 'tao', 'ta'],
    'te': ['teng', 'te'],
    'ti': ['ting', 'tian', 'tiao', 'tie', 'ti'],
    'to': ['tong'],
    'tu': ['tuan', 'tou', 'tui', 'tun', 'tuo', 'tu'],

    'wa': ['wang', 'wai', 'wan', 'wa'],
    'we': ['weng', 'wei', 'wen'],
    'wo': ['wo'],
    'wu': ['wu'],

    'xi': ['xiang', 'xiong', 'xiao', 'xing', 'xian', 'xiu', 'xie', 'xin', 'xia', 'xi'],
    'xu': ['xuan', 'xue', 'xun', 'xu'],

    'ya': ['yang', 'yan', 'yao', 'ya'],
    'ye': ['ye'],
    'yi': ['ying', 'yin', 'yi'],
    'yo': ['yong', 'you', 'yo'],
    'yu': ['yuan', 'yue', 'yun', 'yu'],

    'za': ['zang', 'zao', 'zai', 'zan', 'za'],
    'ze': ['zeng', 'zei', 'zen', 'ze'],
    'zh': ['zhuang', 'zhang', 'zhong', 'zheng', 'zhuai', 'zhuan', 'zhao', 'zhou', 'zhai', 'zhei', 'zhua', 'zhui',
           'zhun', 'zhuo', 'zhen', 'zhan', 'zha', 'zhe', 'zhi', 'zhu'],
    'zi': ['zi'],
    'zo': ['zong', 'zou'],
    'zu': ['zuan', 'zui', 'zun', 'zuo', 'zu']
}

chineseCharacters_dict = {
    'ang': '昂', 'an': '安',
    'ai': '哎',
    'ao': '熬',
    'a': '啊',

    'bang': '帮', 'bai': '白', 'ban': '半', 'bao': '包', 'ba': '吧',
    'beng': '蹦', 'bei': '被', 'ben': '本',
    'bing': '兵', 'bian': '边', 'biao': '标', 'bie': '别', 'bin': '斌', 'bi': '比',
    'bo': '波',
    'bu': '不',

    'cang': '仓', 'cai': '彩', 'can': '参', 'cao': '曹', 'ca': '擦',
    'ceng': '层', 'cen': '岑', 'ce': '册',
    'chuang': '床', 'cheng': '成', 'chang': '长', 'chong': '充', 'chuai': '踹', 'chuan': '传', 'chai': '拆', 'chua': '歘',
    'chui': '吹', 'chun': '春', 'chuo': '戳', 'chan': '产', 'chao': '朝', 'chen': '陈', 'chou': '抽', 'cha': '查', 'che': '车',
    'chi': '吃', 'chu': '出',
    'ci': '次',
    'cong': '从', 'cou': '凑',
    'cuan': '窜', 'cui': '催', 'cun': '存', 'cuo': '错', 'cu': '粗',

    'dang': '当', 'dai': '带', 'dan': '但', 'dao': '到', 'da': '打',
    'deng': '等', 'dei': '得', 'den': '扥', 'de': '的',

    'ding': '定', 'dian': '点', 'diao': '掉', 'dia': '嗲', 'die': '跌', 'diu': '丢', 'di': '第',
    'dong': '动', 'dou': '都',
    'duan': '端', 'dui': '对', 'dun': '顿', 'duo': '多', 'du': '度',

    'eng': '鞥', 'en': '嗯',
    'ei': '诶',
    'er': '二',
    'e': '额',

    'fang': '放', 'fan': '反', 'fa': '发', 'feng': '风',
    'fei': '非',
    'fen': '分',
    'fou': '否', 'fo': '佛',
    'fu': '付',

    'gang': '刚', 'gai': '改', 'gan': '肝', 'gao': '搞', 'ga': '噶',
    'geng': '更', 'gei': '给', 'gen': '跟', 'ge': '个',
    'gong': '攻', 'gou': '够',
    'guang': '光', 'guai': '怪', 'guan': '关', 'gua': '挂', 'gui': '贵', 'gun': '棍', 'guo': '郭', 'gu': '顾',

    'hang': '杭', 'hai': '海', 'han': '喊', 'hao': '好', 'ha': '哈',
    'heng': '哼', 'hei': '黑', 'hen': '很', 'he': '和',
    'hong': '红', 'hou': '后',
    'huang': '黄', 'huai': '坏', 'huan': '换', 'hua': '话', 'hui': '会', 'hun': '混', 'huo': '或', 'hu': '胡',

    'jiang': '将', 'jiong': '囧', 'jing': '晶', 'jian': '减', 'jiao': '叫', 'jia': '加', 'jie': '介', 'jin': '进', 'jiu': '就',
    'ji': '级',
    'juan': '卷', 'jue': '觉', 'jun': '军', 'ju': '句',

    'kang': '抗', 'kai': '开', 'kan': '看', 'kao': '靠', 'ka': '卡',
    'keng': '坑', 'ken': '肯', 'ke': '可',
    'kong': '空', 'kou': '扣',
    'kuang': '框', 'kuai': '快', 'kuan': '款', 'kua': '夸', 'kui': '亏', 'kun': '困', 'kuo': '扩', 'ku': '库',

    'lang': '浪', 'lai': '来', 'lan': '蓝', 'lao': '老', 'la': '拉',
    'leng': '冷', 'lei': '类', 'le': '了',
    'liang': '两', 'ling': '领', 'lian': '连', 'liao': '聊', 'lia': '俩', 'lie': '列', 'lin': '淋', 'liu': '刘', 'li': '里',
    'long': '龙', 'lou': '楼',
    'luan': '卵', 'lue': '略', 'lun': '轮', 'luo': '落', 'lu': '路',
    'lve': '掠', 'lv': '绿',

    'm': '吗',
    'mang': '忙', 'mao': '毛', 'mai': '买', 'man': '满', 'ma': '码',
    'meng': '猛', 'mei': '没', 'men': '们', 'me': '么',
    'ming': '名', 'mian': '面', 'miao': '秒', 'mie': '灭', 'min': '敏', 'miu': '谬', 'mi': '米',
    'mo': '磨', 'mou': '某',
    'mu': '木',

    'nang': '囊', 'nai': '奶', 'nan': '男', 'nao': '闹', 'na': '那',
    'neng': '能', 'nei': '内', 'nen': '嫩', 'ne': '呢',
    'niang': '娘', 'ning': '宁', 'nian': '年', 'niao': '鸟', 'nie': '捏', 'nin': '您', 'niu': '牛', 'ni': '你',
    'nong': '弄', 'nou': '耨',
    'nuan': '暖', 'nuo': '诺', 'nun': '黁', 'nu': '怒',
    'nve': '虐', 'nv': '女',

    'ou': '偶',
    'o': '哦',

    'pang': '胖', 'pao': '跑', 'pai': '拍', 'pan': '盘', 'pa': '怕',
    'peng': '彭', 'pei': '配', 'pen': '喷',
    'ping': '平', 'pian': '骗', 'piao': '飘', 'pie': '撇', 'pin': '品', 'pi': '皮',
    'po': '破', 'pou': '剖',
    'pu': '普',

    'qiong': '穷', 'qiang': '抢', 'qing': '请', 'qiao': '敲', 'qian': '前', 'qie': '切', 'qin': '琴', 'qia': '掐',
    'qiu': '求', 'qi': '起',
    'quan': '全', 'que': '缺', 'qun': '群', 'qu': '去',

    'rang': '让', 'ran': '然', 'rao': '绕',
    'reng': '扔', 'ren': '人', 're': '热',
    'ri': '日',
    'rong': '荣', 'rou': '肉',
    'ruan': '软', 'rui': '瑞', 'run': '润', 'ruo': '若', 'ru': '入',

    'sang': '桑', 'sai': '塞', 'san': '三', 'sao': '骚', 'sa': '撒',
    'seng': '僧', 'sen': '森', 'se': '色',
    'shuang': '爽', 'sheng': '升', 'shang': '上', 'shuai': '衰', 'shuan': '栓', 'shai': '晒', 'shan': '闪', 'shao': '少',
    'shei': '谁', 'shen': '神', 'shua': '刷', 'shui': '水', 'shun': '顺', 'shuo': '说', 'shou': '收', 'sha': '啥', 'she': '设',
    'shi': '是', 'shu': '数',
    'si': '四',
    'song': '送', 'sou': '搜',
    'suan': '算', 'sui': '岁', 'sun': '孙', 'suo': '锁', 'su': '速',

    'tang': '汤', 'tai': '太', 'tan': '谭', 'tao': '套', 'ta': '他',
    'teng': '疼', 'te': '特',
    'ting': '听', 'tian': '天', 'tiao': '条', 'tie': '铁', 'ti': '提', 'tong': '同', 'tuan': '团',
    'tou': '头',
    'tui': '退', 'tun': '吞', 'tuo': '拖', 'tu': '图',

    'wang': '往', 'wai': '外', 'wan': '万', 'wa': '挖',
    'weng': '翁', 'wei': '为', 'wen': '问',
    'wo': '我',
    'wu': '无',

    'xiang': '想', 'xiong': '熊', 'xiao': '小', 'xing': '行', 'xian': '先', 'xiu': '休', 'xie': '写', 'xin': '新', 'xia': '下',
    'xi': '洗',
    'xuan': '选', 'xue': '学', 'xun': '训', 'xu': '需',

    'yang': '养', 'yan': '严', 'yao': '要', 'ya': '呀',
    'ye': '也',
    'ying': '应', 'yin': '因', 'yi': '一',
    'yong': '用', 'you': '有', 'yo': '哟',
    'yuan': '元', 'yue': '月', 'yun': '云', 'yu': '玉',

    'zang': '脏', 'zao': '早', 'zai': '在', 'zan': '咱', 'za': '砸',
    'zeng': '增', 'zei': '贼', 'zen': '怎', 'ze': '则',
    'zhuang': '装', 'zhang': '张', 'zhong': '中', 'zheng': '正', 'zhuai': '拽', 'zhuan': '转', 'zhao': '找', 'zhou': '轴',
    'zhai': '宅', 'zhei': '這', 'zhua': '抓', 'zhui': '追', 'zhun': '准', 'zhuo': '桌', 'zhen': '真', 'zhan': '站', 'zha': '渣',
    'zhe': '这', 'zhi': '只', 'zhu': '主',
    'zi': '子',
    'zong': '总', 'zou': '走',
    'zuan': '钻', 'zui': '最', 'zun': '尊', 'zuo': '做', 'zu': '组'
}

pinyin_shengmu_dict = {
    'a': ['a', '啊'],
    'ang': ['a', '昂'], 'an': ['a', '安'],
    'ai': ['a', '哎'],
    'ao': ['a', '熬'],

    'bang': ['b', '帮'], 'bai': ['b', '白'], 'ban': ['b', '半'], 'bao': ['b', '包'], 'ba': ['b', '吧'],
    'beng': ['b', '蹦'], 'bei': ['b', '被'], 'ben': ['b', '本'],
    'bing': ['b', '兵'], 'bian': ['b', '边'], 'biao': ['b', '标'], 'bie': ['b', '别'], 'bin': ['b', '斌'],
    'bi': ['b', '比'],
    'bo': ['b', '波'],
    'bu': ['b', '不'],

    'cang': ['c', '仓'], 'cai': ['c', '彩'], 'can': ['c', '参'], 'cao': ['c', '曹'], 'ca': ['c', '擦'],
    'ceng': ['c', '层'], 'cen': ['c', '岑'], 'ce': ['c', '册'],
    'chuang': ['ch', '床'], 'cheng': ['ch', '成'], 'chang': ['ch', '长'], 'chong': ['ch', '充'], 'chuai': ['ch', '踹'],
    'chuan': ['ch', '传'], 'chai': ['ch', '拆'], 'chua': ['ch', '歘'], 'chui': ['ch', '吹'], 'chun': ['ch', '春'],
    'chuo': ['ch', '戳'], 'chan': ['ch', '产'], 'chao': ['ch', '朝'], 'chen': ['ch', '陈'], 'chou': ['ch', '抽'],
    'cha': ['ch', '查'], 'che': ['ch', '车'], 'chi': ['ch', '吃'], 'chu': ['ch', '出'],
    'ci': ['c', '次'],
    'cong': ['c', '从'], 'cou': ['c', '凑'],
    'cuan': ['c', '窜'], 'cui': ['c', '催'], 'cun': ['c', '存'], 'cuo': ['c', '错'], 'cu': ['c', '粗'],

    'dang': ['d', '当'], 'dai': ['d', '带'], 'dan': ['d', '但'], 'dao': ['d', '到'], 'da': ['d', '打'],
    'deng': ['d', '等'], 'dei': ['d', '得'], 'den': ['d', '扥'], 'de': ['d', '的'],
    'ding': ['d', '定'], 'dian': ['d', '点'], 'diao': ['d', '掉'], 'dia': ['d', '嗲'], 'die': ['d', '跌'], 'diu': ['d', '丢'],
    'di': ['d', '第'],
    'dong': ['d', '动'], 'dou': ['d', '都'],
    'duan': ['d', '端'], 'dui': ['d', '对'], 'dun': ['d', '顿'], 'duo': ['d', '多'], 'du': ['d', '度'],

    'e': ['e', '额'],
    'ei': ['e', '诶'],
    'eng': ['e', '鞥'], 'en': ['e', '嗯'],
    'er': ['e', '二'],

    'fang': ['f', '放'], 'fan': ['f', '反'], 'fa': ['f', '发'],
    'feng': ['f', '风'], 'fei': ['f', '非'], 'fen': ['f', '分'],
    'fou': ['f', '否'], 'fo': ['f', '佛'],
    'fu': ['f', '付'],

    'gang': ['g', '刚'], 'gai': ['g', '改'], 'gan': ['g', '肝'], 'gao': ['g', '搞'], 'ga': ['g', '噶'],
    'geng': ['g', '更'], 'gei': ['g', '给'], 'gen': ['g', '跟'], 'ge': ['g', '个'], 'gong': ['g', '攻'], 'gou': ['g', '够'],
    'guang': ['g', '光'], 'guai': ['g', '怪'], 'guan': ['g', '关'], 'gua': ['g', '挂'], 'gui': ['g', '贵'],
    'gun': ['g', '棍'], 'guo': ['g', '郭'], 'gu': ['g', '顾'],

    'hang': ['h', '杭'], 'hai': ['h', '海'], 'han': ['h', '喊'], 'hao': ['h', '好'], 'ha': ['h', '哈'],
    'heng': ['h', '哼'], 'hei': ['h', '黑'], 'hen': ['h', '很'], 'he': ['h', '和'],
    'hong': ['h', '红'], 'hou': ['h', '后'],
    'huang': ['h', '黄'], 'huai': ['h', '坏'], 'huan': ['h', '换'], 'hua': ['h', '话'], 'hui': ['h', '会'],
    'hun': ['h', '混'], 'huo': ['h', '或'], 'hu': ['h', '胡'],

    'jiang': ['j', '将'], 'jiong': ['j', '囧'], 'jing': ['j', '晶'], 'jian': ['j', '减'], 'jiao': ['j', '叫'],
    'jia': ['j', '加'], 'jie': ['j', '介'], 'jin': ['j', '进'], 'jiu': ['j', '就'], 'ji': ['j', '级'],
    'juan': ['j', '卷'], 'jue': ['j', '觉'], 'jun': ['j', '军'], 'ju': ['j', '句'],

    'kang': ['k', '抗'], 'kai': ['k', '开'], 'kan': ['k', '看'], 'kao': ['k', '靠'], 'ka': ['k', '卡'],
    'keng': ['k', '坑'], 'ken': ['k', '肯'], 'ke': ['k', '可'],
    'kong': ['k', '空'], 'kou': ['k', '扣'],
    'kuang': ['k', '框'], 'kuai': ['k', '快'], 'kuan': ['k', '款'], 'kua': ['k', '夸'], 'kui': ['k', '亏'],
    'kun': ['k', '困'], 'kuo': ['k', '扩'], 'ku': ['k', '库'],

    'lang': ['l', '浪'], 'lai': ['l', '来'], 'lan': ['l', '蓝'], 'lao': ['l', '老'], 'la': ['l', '拉'],
    'leng': ['l', '冷'], 'lei': ['l', '类'], 'le': ['l', '了'],
    'liang': ['l', '两'], 'ling': ['l', '领'], 'lian': ['l', '连'], 'liao': ['l', '聊'], 'lia': ['l', '俩'],
    'lie': ['l', '列'], 'lin': ['l', '淋'], 'liu': ['l', '刘'], 'li': ['l', '里'],
    'long': ['l', '龙'], 'lou': ['l', '楼'],
    'luan': ['l', '卵'], 'lue': ['l', '略'], 'lun': ['l', '轮'], 'luo': ['l', '落'], 'lu': ['l', '路'],
    'lve': ['l', '掠'], 'lv': ['l', '绿'],

    'm': ['m', '吗'],
    'mang': ['m', '忙'], 'mao': ['m', '毛'], 'mai': ['m', '买'], 'man': ['m', '满'], 'ma': ['m', '码'],
    'meng': ['m', '猛'], 'mei': ['m', '没'], 'men': ['m', '们'], 'me': ['m', '么'],
    'ming': ['m', '名'], 'mian': ['m', '面'], 'miao': ['m', '秒'], 'mie': ['m', '灭'], 'min': ['m', '敏'],
    'miu': ['m', '谬'], 'mi': ['m', '米'],
    'mo': ['m', '磨'], 'mou': ['m', '某'],
    'mu': ['m', '木'],

    'nang': ['n', '囊'], 'nai': ['n', '奶'], 'nan': ['n', '男'], 'nao': ['n', '闹'], 'na': ['n', '那'],
    'neng': ['n', '能'], 'nei': ['n', '内'], 'nen': ['n', '嫩'], 'ne': ['n', '呢'],
    'niang': ['n', '娘'], 'ning': ['n', '宁'], 'nian': ['n', '年'], 'niao': ['n', '鸟'], 'nie': ['n', '捏'],
    'nin': ['n', '您'], 'niu': ['n', '牛'], 'ni': ['n', '你'],
    'nong': ['n', '弄'], 'nou': ['n', '耨'],
    'nuan': ['n', '暖'], 'nuo': ['n', '诺'], 'nun': ['n', '黁'], 'nu': ['n', '怒'],
    'nve': ['n', '虐'], 'nv': ['n', '女'],

    'o': ['o', '哦'],
    'ou': ['o', '偶'],

    'pang': ['p', '胖'], 'pao': ['p', '跑'], 'pai': ['p', '拍'], 'pan': ['p', '盘'], 'pa': ['p', '怕'],
    'peng': ['p', '彭'], 'pei': ['p', '配'], 'pen': ['p', '喷'],
    'ping': ['p', '平'], 'pian': ['p', '骗'], 'piao': ['p', '飘'], 'pie': ['p', '撇'], 'pin': ['p', '品'], 'pi': ['p', '皮'],
    'po': ['p', '破'], 'pou': ['p', '剖'],
    'pu': ['p', '普'],

    'qiong': ['q', '穷'], 'qiang': ['q', '抢'], 'qing': ['q', '请'], 'qiao': ['q', '敲'], 'qian': ['q', '前'],
    'qie': ['q', '切'], 'qin': ['q', '琴'], 'qia': ['q', '掐'], 'qiu': ['q', '求'], 'qi': ['q', '起'],
    'quan': ['q', '全'], 'que': ['q', '缺'], 'qun': ['q', '群'], 'qu': ['q', '去'],

    'rang': ['r', '让'], 'ran': ['r', '然'], 'rao': ['r', '绕'],
    'reng': ['r', '扔'], 'ren': ['r', '人'], 're': ['r', '热'],
    'ri': ['r', '日'],
    'rong': ['r', '荣'], 'rou': ['r', '肉'],
    'ruan': ['r', '软'], 'rui': ['r', '瑞'], 'run': ['r', '润'], 'ruo': ['r', '若'], 'ru': ['r', '入'],

    'sang': ['s', '桑'], 'sai': ['s', '塞'], 'san': ['s', '三'], 'sao': ['s', '骚'], 'sa': ['s', '撒'],
    'seng': ['s', '僧'], 'sen': ['s', '森'], 'se': ['s', '色'],
    'shuang': ['sh', '爽'], 'sheng': ['sh', '升'], 'shang': ['sh', '上'], 'shuai': ['sh', '衰'], 'shuan': ['sh', '栓'],
    'shai': ['sh', '晒'], 'shan': ['sh', '闪'], 'shao': ['sh', '少'], 'shei': ['sh', '谁'], 'shen': ['sh', '神'],
    'shua': ['sh', '刷'], 'shui': ['sh', '水'], 'shun': ['sh', '顺'], 'shuo': ['sh', '说'], 'shou': ['sh', '收'],
    'sha': ['sh', '啥'], 'she': ['sh', '设'], 'shi': ['sh', '是'], 'shu': ['sh', '数'],
    'si': ['s', '四'],
    'song': ['s', '送'], 'sou': ['s', '搜'],
    'suan': ['s', '算'], 'sui': ['s', '岁'], 'sun': ['s', '孙'], 'suo': ['s', '锁'], 'su': ['s', '速'],

    'tang': ['t', '汤'], 'tai': ['t', '太'], 'tan': ['t', '谭'], 'tao': ['t', '套'], 'ta': ['t', '他'],
    'teng': ['t', '疼'], 'te': ['t', '特'],
    'ting': ['t', '听'], 'tian': ['t', '天'], 'tiao': ['t', '条'], 'tie': ['t', '铁'], 'ti': ['t', '提'],
    'tong': ['t', '同'], 'tuan': ['t', '团'], 'tou': ['t', '头'],
    'tui': ['t', '退'], 'tun': ['t', '吞'], 'tuo': ['t', '拖'], 'tu': ['t', '图'],

    'wang': ['w', '往'], 'wai': ['w', '外'], 'wan': ['w', '万'], 'wa': ['w', '挖'],
    'weng': ['w', '翁'], 'wei': ['w', '为'], 'wen': ['w', '问'],
    'wo': ['w', '我'],
    'wu': ['w', '无'],

    'xiang': ['x', '想'], 'xiong': ['x', '熊'], 'xiao': ['x', '小'], 'xing': ['x', '行'], 'xian': ['x', '先'],
    'xiu': ['x', '休'], 'xie': ['x', '写'], 'xin': ['x', '新'], 'xia': ['x', '下'], 'xi': ['x', '洗'],
    'xuan': ['x', '选'], 'xue': ['x', '学'], 'xun': ['x', '训'], 'xu': ['x', '需'],

    'yang': ['y', '养'], 'yan': ['y', '严'], 'yao': ['y', '要'], 'ya': ['y', '呀'],
    'ye': ['y', '也'],
    'ying': ['y', '应'], 'yin': ['y', '因'], 'yi': ['y', '一'],
    'yong': ['y', '用'], 'you': ['y', '有'], 'yo': ['y', '哟'],
    'yuan': ['y', '元'], 'yue': ['y', '月'], 'yun': ['y', '云'], 'yu': ['y', '玉'],

    'zang': ['z', '脏'], 'zao': ['z', '早'], 'zai': ['z', '在'], 'zan': ['z', '咱'], 'za': ['z', '砸'],
    'zeng': ['z', '增'], 'zei': ['z', '贼'], 'zen': ['z', '怎'], 'ze': ['z', '则'],
    'zhuang': ['zh', '装'], 'zhang': ['zh', '张'], 'zhong': ['zh', '中'], 'zheng': ['zh', '正'], 'zhuai': ['zh', '拽'],
    'zhuan': ['zh', '转'], 'zhao': ['zh', '找'], 'zhou': ['zh', '轴'], 'zhai': ['zh', '宅'], 'zhei': ['zh', '這'],
    'zhua': ['zh', '抓'], 'zhui': ['zh', '追'], 'zhun': ['zh', '准'], 'zhuo': ['zh', '桌'], 'zhen': ['zh', '真'],
    'zhan': ['zh', '站'], 'zha': ['zh', '渣'], 'zhe': ['zh', '这'], 'zhi': ['zh', '只'], 'zhu': ['zh', '主'],
    'zi': ['z', '子'],
    'zong': ['z', '总'], 'zou': ['z', '走'],
    'zuan': ['z', '钻'], 'zui': ['z', '最'], 'zun': ['z', '尊'], 'zuo': ['z', '做'], 'zu': ['z', '组']
}
pinyin_shengmu_arr = ['ch', 'sh', 'zh', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
                      'r', 's', 't', 'w', 'x', 'y', 'z']


def __getShenMu(py):
    if py.startswith('a'):
        s = 'a'
    elif py.startswith('b'):
        s = 'b'
    elif py.startswith('c'):
        if len(py) > 1 and py[1:2] == 'h':
            s = 'ch'
        else:
            s = 'c'
    elif py.startswith('d'):
        s = 'd'
    elif py.startswith('e'):
        s = 'e'
    elif py.startswith('f'):
        s = 'f'
    elif py.startswith('g'):
        s = 'g'
    elif py.startswith('h'):
        s = 'h'
    elif py.startswith('j'):
        s = 'j'
    elif py.startswith('k'):
        s = 'k'
    elif py.startswith('l'):
        s = 'l'
    elif py.startswith('m'):
        s = 'm'
    elif py.startswith('n'):
        s = 'n'
    elif py.startswith('o'):
        s = 'o'
    elif py.startswith('p'):
        s = 'p'
    elif py.startswith('q'):
        s = 'q'
    elif py.startswith('r'):
        s = 'r'
    elif py.startswith('s'):
        if len(py) > 1 and py[1:2] == 'h':
            s = 'sh'
        else:
            s = 's'
    elif py.startswith('t'):
        s = 't'
    elif py.startswith('w'):
        s = 'w'
    elif py.startswith('x'):
        s = 'x'
    elif py.startswith('y'):
        s = 'y'
    elif py.startswith('z'):
        if len(py) > 1 and py[1:2] == 'h':
            s = 'zh'
        else:
            s = 'z'
    else:
        s = py
    return s


def __getPinYinDict():
    # 根据 pinyin_dict 和 chineseCharacters_dict 生成 拼音对应的声母汉字字典 例如：{'zuo': ['z', '做'],……}
    smap = {}
    for key in pinyin_dict.keys():
        s = __getShenMu(key)
        arr = pinyin_dict[key]
        for item in arr:
            chineseCharacters = chineseCharacters_dict[item]
            smap[item] = [s, chineseCharacters]
    print(smap)


def __check1():
    # 检查 chineseCharacters_dict 中汉字是否重复
    m = {}
    for key in chineseCharacters_dict.keys():
        v = chineseCharacters_dict[key]
        if v not in m.keys():
            m[v] = 1
        else:
            m[v] = m[v] + 1
    for k in m.keys():
        v = m[k]
        if v > 1:
            print(k)


def __check2():
    # 检查 pinyin_shengmu_dict 中汉字是否重复
    m = {}
    for key in pinyin_shengmu_dict.keys():
        arr = pinyin_shengmu_dict[key]
        v = arr[1]
        if v not in m.keys():
            m[v] = 1
        else:
            m[v] = m[v] + 1
    for k in m.keys():
        v = m[k]
        if v > 1:
            print(k)


def __getShenMuArr():
    # 获取全部声母
    shengMuArr = []
    for k in pinyin_shengmu_dict.keys():
        arr = pinyin_shengmu_dict[k]
        s = arr[0]
        if s not in shengMuArr:
            shengMuArr.append(s)
    shengMuArr = sorted(shengMuArr, key=lambda i: len(i), reverse=True)
    print(shengMuArr)


################################# 上面是静态字典和生成静态字典的工具 ，下面是提供给外部的公用方法 ###################################################################

def __checkShemMu(x):
    if x is None or len(x) == 0:
        return False, None
    s = x[:1]
    if len(x) > 1 and x[1:2] == 'h':
        s = x[:2]

    if s in pinyin_shengmu_arr:
        return True, s
    else:
        return False, None


def __checkPinYin(x):
    """ 检查是否是拼音开头，并返回 开头的拼音 """
    if x is None or len(x) == 0:
        return False, None
    if len(x) == 1:
        if x in ['a', 'e', 'm', 'o']:
            return True, x
        else:
            return False, None
    else:
        s = x[:2]
        if s not in pinyin_dict.keys():
            return False, None
        itemArr = pinyin_dict[s]
        isStart = False
        start = None
        for item in itemArr:
            if x.startswith(item):
                isStart = True
                start = item
                break
        return isStart, start


def __getChineseCharactersArr(x, pyArr, smArr, cArr, pysmArr):
    """
        姓名拼音转换为 拼音数组,声母数组,汉字数组

    :param x: 拼音
    :param pyArr: 拼音结果集
    :param smArr: 声母结果集
    :param cArr: 汉字结果集
    :param pysmArr: 拼音声母标志结果集，1：拼音，2：声母缩写，例如 [1,1,2] 是 [拼音，拼音，声母缩写]
    """
    if x is None or len(x) == 0:
        # x 都检查完了，返回结果
        return pyArr, smArr, cArr, pysmArr
    # 先检查是否拼音开头
    check, py = __checkPinYin(x)
    if check:
        pysmDictArr = pinyin_shengmu_dict[py]
        pyArr.append(py)
        smArr.append(pysmDictArr[0])
        cArr.append(pysmDictArr[1])
        pysmArr.append(1)
        x = x[len(py):]
        return __getChineseCharactersArr(x, pyArr, smArr, cArr, pysmArr)
    else:
        # 再检查是否声母缩写开头
        check, sm = __checkShemMu(x)
        if check:
            pyArr.append(sm)
            smArr.append(sm)
            cArr.append(sm)
            pysmArr.append(2)
            x = x[len(sm):]
            return __getChineseCharactersArr(x, pyArr, smArr, cArr, pysmArr)
        else:
            # 既不是拼音开头，又不是声母缩写开头，则不是汉字；只要有一个字不是汉字，则返回空，校验失败
            return [], [], [], []


def isLCS(x, y):
    # 有一个是空，返回 False
    if x is None or y is None:
        return False

    # 统一去除字母之外的符号数字，转小写，进行比较
    x = re.sub("[^A-Za-z]", "", x).lower()
    y = re.sub("[^A-Za-z]", "", y).lower()

    # 有一个是空，返回 False
    if len(x) == 0 or len(y) == 0:
        return False

    xpyArr, xsmArr, xcArr, xpysmArr = __getChineseCharactersArr(x, [], [], [], [])
    # 解析出来的是空数组，返回 False
    if len(xpyArr) == 0:
        return False
    # x 解析出来的拼音，声母，汉字 字数不一致，返回 False
    if not (len(xpyArr) == len(xsmArr) == len(xcArr) == len(xpysmArr)):
        return False

    ypyArr, ysmArr, ycArr, ypysmArr = __getChineseCharactersArr(y, [], [], [], [])
    # 解析出来的是空数组，返回 False
    if len(ypyArr) == 0:
        return False
    # y 解析出来的拼音，声母，汉字 字数不一致，返回 False
    if not (len(ypyArr) == len(ysmArr) == len(ycArr) == len(ypysmArr)):
        return False
    # x和 y 解析出来的拼音字数不一致，返回 False
    if len(xpyArr) != len(ypyArr):
        return False

    # 解析出来的 姓 不一样，返回 False
    if xpyArr[0] != ypyArr[0]:
        return False
    # 姓一致，比较名
    for i in range(1, len(xcArr)):
        # 有一个声母不一致，则返回 False
        if xsmArr[i] != ysmArr[i]:
            return False
        # 两个都是拼音，比较汉字  . 若至少其一是声母简写，则通过 , 举例： tan 和 t
        if xpysmArr[i] == 1 and ypysmArr[i] == 1:
            # 若汉字不一样，则返回 False , 举例： tan 和 tao
            if xcArr[i] != ycArr[i]:
                return False

    return True


if __name__ == '__main__':
    x = 'Ding, Yanfeng'
    y = 'ding,yangfeng'
    print(isLCS(x, y))
    print(lcs.isLCS(x, y))
